数组中只有一个数出现奇数次 | 利用异或最高效

一、背景

题意：一个数组有奇数个元素，其中只有一个元素出现一次，其它都出现了2次

方案A：利用hashMap存储出现的次数，然后遍历，复杂度O(3/2N)=O(N);
方案B：利用bitmap,根据数组元素的大小确定位置，做取反(0->1->0);
方案C：利用异或的特性快速找出，最简单，高效;

二、异或

a^a=0
0^a=a
异或支持：交换率、结合率
因此：
a^b^c^b^c=a^(b^b)^(c^c)=a

三、代码

public static void main(String[] args) {
    int[] mayDup = {1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int res = mayDup[0];
    for (int i = 1; i < mayDup.length; i++) {
        System.out.print("res^mayDup[i]: " + res + "^" + mayDup[i]);
        res ^= mayDup[i];
        System.out.println("=" + res);
    }
    System.out.println(res);
}

四、后记

这只是一个场景的妙用，实际当中很难遇到这种情况。
所以不管什么时候还是得多去刷题，没事刷几道，熟然生巧。